package leetcode_1301_1400;

import java.util.Arrays;

public class LeeCode_1335 {
    public static void main(String[] args) {
        System.out.println(minDifficulty(new int[]{6, 5, 4, 3, 2, 1}, 2));
    }
    private static int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        int[][] dp = new int[d + 1][n];
        if (n < d)
            return -1;
        for (int[] ints : dp) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        int ma = 0;
        for (int i = 0; i < n; i++) {
            ma = Math.max(ma, jobDifficulty[i]);
            dp[0][i] = ma;
        }
        for (int i = 1; i < d; i++) {
            for (int j = i; j < n; j++) {
                ma = 0;
                for(int k = j; k >= i; k--){
                    ma = Math.max(ma, jobDifficulty[k]);
                    dp[i][j] = Math.min(dp[i][j], ma + dp[i - 1][k - 1]);
                }
            }
        }
        return dp[d - 1][n - 1];
    }
}
